/**
 *  @file mergelink.c
 *  @desc 实现单链表的基本操作及两个带头节点单链表的合并功能
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-23 16:59
 *  @version 1.0
 */

#include <stdlib.h>
#include <stdio.h>

// 单链表节点结构体定义
typedef struct node {
    int data;           // 数据域，存储节点的值
    struct node *next;  // 指针域，指向下一个节点
} node, *link;

/**
 * @brief 创建一个新节点
 * @param value 节点数据值
 * @return 返回新节点指针，失败返回NULL
 */
link createNode(int value) {
    link newNode = (link) malloc(sizeof(node));
    if (newNode == NULL) return NULL;  // 内存分配失败返回NULL
    newNode->next = NULL;
    newNode->data = value;
    return newNode;
}

/**
 * @brief 初始化带头节点的空链表
 * @param head 传入头节点指针的地址，初始化后指向新创建的头节点
 */
void initNode(link *head) {
    link newNode = createNode(0);  // 创建头节点，数据域设为0（无实际数据）
    if (newNode == NULL) return;   // 创建失败直接返回
    *head = newNode;
}

/**
 * @brief 打印链表中除头节点外所有节点的值
 * @param head 链表头节点指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;  // 空链表或无有效节点直接返回
    link cur = head->next;  // 跳过头节点，开始打印有效数据
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 在头节点之后插入新节点（头插法）
 * @param head 链表头节点指针
 * @param value 插入节点的数据值
 */
void istHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = head->next;  // 新节点指向原第一个节点
    head->next = newNode;        // 头节点指向新节点
}

/**
 * @brief 在链表尾部插入新节点（尾插法）
 * @param head 链表头节点指针
 * @param value 插入节点的数据值
 */
void istTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    link cur = head;
    while (cur->next != NULL) {  // 遍历找到尾节点
        cur = cur->next;
    }
    cur->next = newNode;  // 尾节点指向新节点
}

/**
 * @brief 按位置删除节点（头节点不删除，位置从1开始）
 * @param head 链表头节点指针
 * @param pos  要删除节点的位置
 */
void delByPos(link head, int pos) {
    if (head == NULL || head->next == NULL) return;  // 空链表或无节点
    link cur = head->next;
    link delPre = head;  // 要删除节点的前驱
    int idx = 1;

    while (cur != NULL && idx < pos) {
        delPre = cur;
        cur = cur->next;
        idx++;
    }

    if (cur == NULL) return;  // 位置越界，不删除

    delPre->next = cur->next;  // 前驱跳过当前节点
    free(cur);                 // 释放当前节点内存
}

/**
 * @brief 释放整个链表所有节点内存，包括头节点
 * @param head 链表头节点指针的地址，释放后指向NULL
 */
void destroy(link *head) {
    if (head == NULL || *head == NULL) return;
    link cur = (*head)->next;
    while (cur != NULL) {
        link temp = cur->next;
        free(cur);
        cur = temp;
    }
    (*head)->next = NULL;
    free(*head);
    *head = NULL;
}

/**
 * @brief 合并两个带头节点的单链表，将 lb 链表数据接到 la 链表尾部，并释放 lb 头节点
 * @param la 第一个链表头节点指针
 * @param lb 第二个链表头节点指针
 * @return 合并后的链表头节点指针（即 la）
 *
 * @note 假设两个链表均带头节点，且不为空
 */
link mergeLink(link la, link lb) {
    if (la == NULL || la->next == NULL) return lb;  // la为空或无数据，返回lb
    if (lb == NULL || lb->next == NULL) return la;  // lb为空或无数据，返回la

    link pa = la;
    while (pa->next != NULL) {  // 找到 la 的尾节点
        pa = pa->next;
    }

    pa->next = lb->next;  // 将 lb 的数据节点接到 la 的尾部

    free(lb);  // 只释放 lb 头节点，防止内存泄漏且不破坏合并后的链表结构

    return la;
}

/**
 * @brief 测试程序入口，演示链表操作和合并功能
 */
int main() {
    link head = NULL;
    initNode(&head);
    istTail(head, 1);
    istTail(head, 2);
    istTail(head, 3);

    link head1 = NULL;
    initNode(&head1);
    istTail(head1, 1);
    istTail(head1, 2);
    istTail(head1, 3);

    // 合并链表，head1 的数据接到 head 后面
    link result = mergeLink(head, head1);

    printList(result);  // 打印合并后的链表数据

    // 释放链表内存
    destroy(&result);

    return 0;
}
